/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package searchAlgs;


import Graph.Edge;
import Graph.Graph;
import Graph.Vertex;
import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author Ruan
 */
public class AlgPrim {
    
    private Graph graph = new Graph();
    private Map<Integer,Integer> chave = new HashMap<Integer,Integer>();
    private Map<Integer,Vertex> precursor = new HashMap<Integer, Vertex>();
    private Map<Integer,Vertex> q = new HashMap<Integer, Vertex>();
    private Vertex r,u,v;
    
    public AlgPrim(Graph g,Vertex v){
        this.r =v;
        this.graph = g;
    }
    
    public void doPrim(){
        for(int i = 1;i<=graph.getVertexes().size();i++){
            q.put(graph.getVertexes().get(i).getId(),graph.getVertexes().get(i));
            chave.put(graph.getVertexes().get(i).getId(), 0);
        }
        chave.remove(r.getId());
        chave.put(r.getId(),0);
        precursor.put(r.getId(),null);
        this.u = r;
        while(!q.isEmpty()){
            v = removeMin(this.u);
            for(int i = 0;i < v.getEdges().size();i++){
                if((q.containsKey(v.getEdges().get(i).getVj().getId())) && (v.getEdges().get(i).getCost() < chave.get(v.getEdges().get(i).getVj().getId()))){
                    precursor.remove(v.getEdges().get(i).getVj().getId());
                    precursor.put(v.getEdges().get(i).getVj().getId(), v);
                    chave.remove(v.getEdges().get(i).getVj().getId());
                    chave.put(v.getEdges().get(i).getVj().getId(), v.getEdges().get(i).getCost());
                    
                }
            }
        }
        for(int i = 1;i<=chave.size();i++){
            System.out.print("Vértice "+graph.getVertexes().get(precursor.get(i).getId()));
            System.out.print("ligado ao Vértice "+graph.getVertexes().get(i).getId());
            System.out.println("com custo = "+chave.get(i));
        }
    }
    
    public Vertex removeMin(Vertex u){
        int a = 0;
        Edge aux = new Edge(u.getEdges().get(0).getVi(),u.getEdges().get(0).getVj(),(int)Double.POSITIVE_INFINITY);
        for(int i = 0;i<u.getEdges().size();i++){
            if(this.q.containsKey(u.getEdges().get(i).getVj().getId())){
                if(u.getEdges().get(i).getCost()<aux.getCost()){
                    aux = u.getEdges().get(i);
                    aux.setCost(u.getEdges().get(i).getCost());
                    
                }
                a++;
            }     
        }
        if(a>0){
            this.q.remove(this.u.getId());      
            this.u = new Vertex(aux.getVj().getId());
            this.u.setEdges(aux.getVj().getEdges());
            return aux.getVj();
        }else{
            boolean b = true;
            while(b){
                u = this.precursor.get(u.getId());
                for(int i = 0;i<=u.getEdges().size();i++){
                    if(this.q.containsKey(u.getEdges().get(i).getVj().getId())){
                       aux = u.getEdges().get(i);
                       b = false;
                    }
                    
                }
            }
            return aux.getVj();
        }
    }
}